import java.util.ArrayList;
import java.util.List;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 063. 替换单词
 * @author: WXY
 * @create: 2023-01-07 09:45
 * @Version 1.0
 **/
public class offer_twentyone2_replaceWords {

    public static String replaceWords(List<String> dictionary, String sentence) {
        TrieNode node = new TrieNode();
        for (String s : dictionary) {
            node.insert(s);
        }
        String[] sp = sentence.split(" ");

        for (int i = 0; i < sp.length; i++) {
            String str = node.get(sp[i]);
            if (str != null) {
                sp[i] = str;
            }
        }
        return String.join(" ", sp);
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("cat");
        list.add("bat");
        list.add("rat");
        String s = "the cattle was rattled by the battery";
        String s1 = replaceWords(list, s);
        System.out.println(s1);
    }

    static class Trie {
        Trie[] next;
        String word;

        public Trie() {
            next = new Trie[26];
            word = null;
        }

    }

    public static class TrieNode {
        private Trie root = new Trie();

        public void insert(String str) {
            Trie node = root;
            for (char ch : str.toCharArray()) {
                if (node.next[ch - 'a'] == null) {
                    node.next[ch - 'a'] = new Trie();
                }
                node = node.next[ch - 'a'];
            }
            node.word = str;
        }

        public String get(String str) {
            Trie node = root;
            for (char ch : str.toCharArray()) {
                if (node.word != null) {
                    break;
                }
                if (node.next[ch - 'a'] == null) {
                    return null;
                }
                node = node.next[ch - 'a'];
            }
            return node.word;
        }

    }
}
